Concepedia

Concept

network flows

Parents

Children

13.2K

Publications

739K

Citations

29.2K

Authors

4.2K

Institutions

Dynamic Polymatroidal Network Flows

1981 - 1987

The 1981–1987 period expanded the classical network flow framework by incorporating set-based (polymatroidal) constraints and time-evolving costs, enabling dynamic planning and optimization for convex/concave objectives with polynomial-time solvability. This era also delivered algorithmic breakthroughs that improved scalability, from new max-flow formulations and faster bipartite reductions to distributed computation strategies, and it began to leverage stochastic models to enable tractable performance analysis of larger systems through product-form representations and asymptotic expansions. Additionally, resilience considerations under uncertainty emerged, guiding fault-tolerant routings and performance bounds under failures or attacks and informing robust network design.

Generalized and dynamic flow models broaden the classical network flow framework to include set-based (polymatroidal) constraints and time-evolving costs, enabling dynamic planning and convex/concave objectives with polynomial-time solvability [1], [2], [15], [6], [7].

Algorithmic innovations improved complexity and scalability: from new max-flow formulations and fast bipartite algorithms to reductions and distributed arborescence computations [8], [4], [19], [20], [9].

Stochastic models for closed Markovian networks with product-form distributions, integral representations, and asymptotic expansions enabling tractable performance analysis of large systems [3], [5], [12].

Studies of fault-tolerant routings, performance bounds under failures, and strategic attack/defense inform design for resilience under uncertainty [17], [18], [14], [9].

Deterministic QoS Networking

1988 - 1994

Dynamic Network Flows

1995 - 2001

Resource-Constrained Network Flows

2002 - 2010

Programmable Flow Paradigm

2011 - 2017

Dynamic Spatio-Temporal Graph Forecasting

2018 - 2024